This invention relates to a memory device, and more particularly to a memory device having a built-in circuit which permits access to data stored in the memory device and at the same time performs marking for the purpose of effecting garbage collection.
Computers are now being widely utilized more and more not only in the field of numerical calculations but also in various application fields such as artificial intelligence and natural lagnuage processing. With the ever-increasing utilization of the computers in these application fields, there arises the necessity of a data structure which makes the structure of storage areas be changed dynamically at the time of executing a program for use in the associated processings. For that purpose, dynamic management of storage areas is required. In the case of such dynamic storage area management, a method called garbage collection is used in which storage areas, which have become unnecessary, are collected for the purpose of reuse thereof. According to one form of the garbage collection method for collecting storage areas which have become unnecessary, storage areas in use are marked, so that storage areas which have not been marked, that is, unnecessary storage areas are collected. The aforesaid garbage collection method is described in Knuth, D. E.: The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addision-Wesley, 1973.
The semiconductor technology has made a great progress, and, because of this great progress of the semiconductor technology, the storage capacity of memory devices has been greatly increased. Thus, the prior art method described above is defective in that a long period of time is required for effecting the garbage collection.